home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 2000 July: Mac OS SDK / Dev.CD Jul 00 SDK2.toast / Development Kits / Cross Platform / QuickTime 4.1.2 Windows SDK / CIncludes / AVLTree.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-04-12  |  14.7 KB  |  351 lines  |  [TEXT/R*ch]
  1. /*
  2.      File:        AVLTree.h
  3.  
  4.      Contains:    Prototypes for routines which create, destroy, allow for
  5.  
  6.      Version:    Technology:    
  7.                  Release:    QuickTime 4.1
  8.  
  9.      Copyright:    (c) 1999 by Apple Computer, Inc., all rights reserved.
  10.  
  11.      Bugs?:        For bug reports, consult the following page on
  12.                  the World Wide Web:
  13.  
  14.                      http://developer.apple.com/bugreporter/
  15.  
  16. */
  17. #ifndef __AVLTREE__
  18. #define __AVLTREE__
  19.  
  20. #ifndef __MACTYPES__
  21.     #include <MacTypes.h>
  22. #endif
  23.  
  24. #ifndef __MIXEDMODE__
  25.     #include <MixedMode.h>
  26. #endif
  27.  
  28.  
  29. /* The visit stage for AVLWalk() walkProcs */
  30.  
  31.  
  32. #if PRAGMA_ONCE
  33. #pragma once
  34. #endif
  35.  
  36. #ifdef __cplusplus
  37. extern "C" {
  38. #endif
  39.  
  40. #if PRAGMA_IMPORT
  41. #pragma import on
  42. #endif
  43.  
  44. #if PRAGMA_STRUCT_ALIGN
  45.     #pragma options align=mac68k
  46. #elif PRAGMA_STRUCT_PACKPUSH
  47.     #pragma pack(push, 2)
  48. #elif PRAGMA_STRUCT_PACK
  49.     #pragma pack(2)
  50. #endif
  51.  
  52.  
  53. typedef UInt16 AVLVisitStage;
  54. enum {
  55.     kAVLPreOrder                = 0,
  56.     kAVLInOrder                    = 1,
  57.     kAVLPostOrder                = 2
  58. };
  59.  
  60. /* The order the tree is walked or disposed of. */
  61.  
  62. typedef UInt16 AVLOrder;
  63. enum {
  64.     kLeftToRight                = 0,
  65.     kRightToLeft                = 1
  66. };
  67.  
  68. /* The type of the node being passed to a callback proc. */
  69.  
  70. typedef UInt16 AVLNodeType;
  71. enum {
  72.     kAVLIsTree                    = 0,
  73.     kAVLIsLeftBranch            = 1,
  74.     kAVLIsRightBranch            = 2,
  75.     kAVLIsLeaf                    = 3,
  76.     kAVLNullNode                = 4
  77. };
  78.  
  79. enum {
  80.     errItemAlreadyInTree        = -960,
  81.     errNotValidTree                = -961,
  82.     errItemNotFoundInTree        = -962,
  83.     errCanNotInsertWhileWalkProcInProgress = -963,
  84.     errTreeIsLocked                = -964
  85. };
  86.  
  87. /*    The structure of a tree.  It's opaque; don't assume it's 36 bytes in size.*/
  88.  
  89. struct AVLTreeStruct {
  90.     OSType                             signature;
  91.     unsigned long                     privateStuff[8];
  92. };
  93. typedef struct AVLTreeStruct            AVLTreeStruct;
  94.  
  95. typedef AVLTreeStruct *                    AVLTreePtr;
  96. /*
  97.       Every tree must have a function which compares the data for two items and returns < 0, 0, or >0
  98.       for the items - < 0 if the first item is 'before' the second item according to some criteria,
  99.       == 0 if the two items are identical according to the criteria, or > 0 if the first item is
  100.       'after' the second item according to the criteria.  The comparison function is also passed the
  101.       node type, but most of the time this can be ignored.
  102. */
  103. typedef CALLBACK_API( SInt32 , AVLCompareItemsProcPtr )(AVLTreePtr tree, const void *i1, const void *i2, AVLNodeType nd_typ);
  104. /*
  105.       Every tree must have a itemSizeProc; this routine gets passed a pointer to the item's data and
  106.       returns the size of the data.  If a tree contains records of a fixed size, this function can
  107.       just return sizeof( that-struct ); otherwise it should calculate the size of the item based on
  108.       the data for the item.
  109. */
  110. typedef CALLBACK_API( UInt32 , AVLItemSizeProcPtr )(AVLTreePtr tree, const void *itemPtr);
  111. /*
  112.       A tree may have an optional disposeItemProc, which gets called whenever an item is removed
  113.       from the tree ( via AVLRemove() or when AVLDispose() deletes all of the items in the tree ).
  114.       This might be useful if the nodes in the tree own 'resources'  ( like, open files ) which
  115.       should be released before the item is removed.
  116. */
  117. typedef CALLBACK_API( void , AVLDisposeItemProcPtr )(AVLTreePtr tree, const void *dataP);
  118. /*
  119.       The common way to iterate across all of the items in a tree is via AVLWalk(), which takes
  120.       a walkProcPtr.  This function will get called for every item in the tree three times, as
  121.       the tree is being walked across.  First, the walkProc will get called with visitStage ==
  122.       kAVLPreOrder, at which point internally the node of the tree for the given data has just
  123.       been reached.  Later, this function will get called with visitStage == kAVLInOrder, and
  124.       lastly this function will get called with visitStage == kAVLPostOrder.
  125.       The 'minimum' item in the tree will get called with visitStage == kInOrder first, followed
  126.       by the 'next' item in the tree, up until the last item in the tree structure is called.
  127.       In general, you'll only care about calls to this function when visitStage == kAVLInOrder.
  128. */
  129. typedef CALLBACK_API( OSErr , AVLWalkProcPtr )(AVLTreePtr tree, const void *dataP, AVLVisitStage visitStage, AVLNodeType node, UInt32 level, SInt32 balance, void *refCon);
  130. typedef STACK_UPP_TYPE(AVLCompareItemsProcPtr)                     AVLCompareItemsUPP;
  131. typedef STACK_UPP_TYPE(AVLItemSizeProcPtr)                         AVLItemSizeUPP;
  132. typedef STACK_UPP_TYPE(AVLDisposeItemProcPtr)                     AVLDisposeItemUPP;
  133. typedef STACK_UPP_TYPE(AVLWalkProcPtr)                             AVLWalkUPP;
  134. #if OPAQUE_UPP_TYPES
  135.     EXTERN_API(AVLCompareItemsUPP)
  136.     NewAVLCompareItemsUPP           (AVLCompareItemsProcPtr    userRoutine);
  137.  
  138.     EXTERN_API(AVLItemSizeUPP)
  139.     NewAVLItemSizeUPP               (AVLItemSizeProcPtr        userRoutine);
  140.  
  141.     EXTERN_API(AVLDisposeItemUPP)
  142.     NewAVLDisposeItemUPP           (AVLDisposeItemProcPtr    userRoutine);
  143.  
  144.     EXTERN_API(AVLWalkUPP)
  145.     NewAVLWalkUPP                   (AVLWalkProcPtr            userRoutine);
  146.  
  147.     EXTERN_API(void)
  148.     DisposeAVLCompareItemsUPP       (AVLCompareItemsUPP        userUPP);
  149.  
  150.     EXTERN_API(void)
  151.     DisposeAVLItemSizeUPP           (AVLItemSizeUPP            userUPP);
  152.  
  153.     EXTERN_API(void)
  154.     DisposeAVLDisposeItemUPP       (AVLDisposeItemUPP        userUPP);
  155.  
  156.     EXTERN_API(void)
  157.     DisposeAVLWalkUPP               (AVLWalkUPP                userUPP);
  158.  
  159.     EXTERN_API(SInt32)
  160.     InvokeAVLCompareItemsUPP       (AVLTreePtr                tree,
  161.                                     const void *            i1,
  162.                                     const void *            i2,
  163.                                     AVLNodeType                nd_typ,
  164.                                     AVLCompareItemsUPP        userUPP);
  165.  
  166.     EXTERN_API(UInt32)
  167.     InvokeAVLItemSizeUPP           (AVLTreePtr                tree,
  168.                                     const void *            itemPtr,
  169.                                     AVLItemSizeUPP            userUPP);
  170.  
  171.     EXTERN_API(void)
  172.     InvokeAVLDisposeItemUPP           (AVLTreePtr                tree,
  173.                                     const void *            dataP,
  174.                                     AVLDisposeItemUPP        userUPP);
  175.  
  176.     EXTERN_API(OSErr)
  177.     InvokeAVLWalkUPP               (AVLTreePtr                tree,
  178.                                     const void *            dataP,
  179.                                     AVLVisitStage            visitStage,
  180.                                     AVLNodeType                node,
  181.                                     UInt32                    level,
  182.                                     SInt32                    balance,
  183.                                     void *                    refCon,
  184.                                     AVLWalkUPP                userUPP);
  185.  
  186. #else
  187.     enum { uppAVLCompareItemsProcInfo = 0x00002FF0 };                 /* pascal 4_bytes Func(4_bytes, 4_bytes, 4_bytes, 2_bytes) */
  188.     enum { uppAVLItemSizeProcInfo = 0x000003F0 };                     /* pascal 4_bytes Func(4_bytes, 4_bytes) */
  189.     enum { uppAVLDisposeItemProcInfo = 0x000003C0 };                 /* pascal no_return_value Func(4_bytes, 4_bytes) */
  190.     enum { uppAVLWalkProcInfo = 0x000FEBE0 };                         /* pascal 2_bytes Func(4_bytes, 4_bytes, 2_bytes, 2_bytes, 4_bytes, 4_bytes, 4_bytes) */
  191.     #define NewAVLCompareItemsUPP(userRoutine)                         (AVLCompareItemsUPP)NewRoutineDescriptor((ProcPtr)(userRoutine), uppAVLCompareItemsProcInfo, GetCurrentArchitecture())
  192.     #define NewAVLItemSizeUPP(userRoutine)                             (AVLItemSizeUPP)NewRoutineDescriptor((ProcPtr)(userRoutine), uppAVLItemSizeProcInfo, GetCurrentArchitecture())
  193.     #define NewAVLDisposeItemUPP(userRoutine)                         (AVLDisposeItemUPP)NewRoutineDescriptor((ProcPtr)(userRoutine), uppAVLDisposeItemProcInfo, GetCurrentArchitecture())
  194.     #define NewAVLWalkUPP(userRoutine)                                 (AVLWalkUPP)NewRoutineDescriptor((ProcPtr)(userRoutine), uppAVLWalkProcInfo, GetCurrentArchitecture())
  195.     #define DisposeAVLCompareItemsUPP(userUPP)                         DisposeRoutineDescriptor(userUPP)
  196.     #define DisposeAVLItemSizeUPP(userUPP)                             DisposeRoutineDescriptor(userUPP)
  197.     #define DisposeAVLDisposeItemUPP(userUPP)                         DisposeRoutineDescriptor(userUPP)
  198.     #define DisposeAVLWalkUPP(userUPP)                                 DisposeRoutineDescriptor(userUPP)
  199.     #define InvokeAVLCompareItemsUPP(tree, i1, i2, nd_typ, userUPP)  (SInt32)CALL_FOUR_PARAMETER_UPP((userUPP), uppAVLCompareItemsProcInfo, (tree), (i1), (i2), (nd_typ))
  200.     #define InvokeAVLItemSizeUPP(tree, itemPtr, userUPP)             (UInt32)CALL_TWO_PARAMETER_UPP((userUPP), uppAVLItemSizeProcInfo, (tree), (itemPtr))
  201.     #define InvokeAVLDisposeItemUPP(tree, dataP, userUPP)             CALL_TWO_PARAMETER_UPP((userUPP), uppAVLDisposeItemProcInfo, (tree), (dataP))
  202.     #define InvokeAVLWalkUPP(tree, dataP, visitStage, node, level, balance, refCon, userUPP)  (OSErr)CALL_SEVEN_PARAMETER_UPP((userUPP), uppAVLWalkProcInfo, (tree), (dataP), (visitStage), (node), (level), (balance), (refCon))
  203. #endif
  204. /* support for pre-Carbon UPP routines: NewXXXProc and CallXXXProc */
  205. #define NewAVLCompareItemsProc(userRoutine)                     NewAVLCompareItemsUPP(userRoutine)
  206. #define NewAVLItemSizeProc(userRoutine)                         NewAVLItemSizeUPP(userRoutine)
  207. #define NewAVLDisposeItemProc(userRoutine)                         NewAVLDisposeItemUPP(userRoutine)
  208. #define NewAVLWalkProc(userRoutine)                             NewAVLWalkUPP(userRoutine)
  209. #define CallAVLCompareItemsProc(userRoutine, tree, i1, i2, nd_typ) InvokeAVLCompareItemsUPP(tree, i1, i2, nd_typ, userRoutine)
  210. #define CallAVLItemSizeProc(userRoutine, tree, itemPtr)            InvokeAVLItemSizeUPP(tree, itemPtr, userRoutine)
  211. #define CallAVLDisposeItemProc(userRoutine, tree, dataP)        InvokeAVLDisposeItemUPP(tree, dataP, userRoutine)
  212. #define CallAVLWalkProc(userRoutine, tree, dataP, visitStage, node, level, balance, refCon) InvokeAVLWalkUPP(tree, dataP, visitStage, node, level, balance, refCon, userRoutine)
  213. /*
  214.       Create an AVL tree.  The compareItemsProc and the sizeItemProc are required; disposeItemProc is
  215.       optional and can be nil.  The refCon is stored with the list, and is passed back to the
  216.       compareItemsProc, sizeItemProc, and disposeItemsProc calls.  The allocation of the tree ( and all
  217.       nodes later added to the list with AVLInsert ) will be created in what is the current zone at the
  218.       time AVLInit() is called.  Always call AVLDispose() to dispose of a list created with AVLInit().
  219. */
  220. EXTERN_API( OSErr )
  221. AVLInit                            (UInt32                 flags,
  222.                                  AVLCompareItemsUPP     compareItemsProc,
  223.                                  AVLItemSizeUPP         sizeItemProc,
  224.                                  AVLDisposeItemUPP         disposeItemProc,
  225.                                  void *                    refCon,
  226.                                  AVLTreePtr *            tree)                                THREEWORDINLINE(0x303C, 0x0C01, 0xAA80);
  227.  
  228. /*
  229.       Dispose of an AVL tree.  This will dispose of each item in the tree in the order specified,
  230.       call the tree's disposeProc proc for each item, and then dispose of the space allocated for
  231.       the tree itself.
  232. */
  233. EXTERN_API( OSErr )
  234. AVLDispose                        (AVLTreePtr *            tree,
  235.                                  AVLOrder                 order)                                THREEWORDINLINE(0x303C, 0x0302, 0xAA80);
  236.  
  237. /*
  238.       Iterate across all of the items in the tree, in the order specified.  kLeftToRight is
  239.       basically lowest-to-highest order, kRightToLeft is highest-to-lowest order.  For each
  240.       node in the tree, it will call the walkProc with three messages ( at the appropriate 
  241.       time ).  First, with kAVLPreOrder when the walking gets to this node in the tree,
  242.       before handling either the left or right subtree, secondly, with kAVLInOrder after
  243.       handling one subtree but before handling the other, and lastly with kAVLPostOrder after
  244.       handling both subtrees.  If you want to handle items in order, then only do something
  245.       if the visit stage is kAVLInOrder.  You can only call AVLRemove() from inside a walkProc
  246.       if visit stage is kAVLPostOrder ( because if you remove a node during the pre or in order
  247.       stages you will corrupt the list ) OR if you return a non-zero result from the walkProc
  248.       call which called AVLRemove() to immediately terminate the walkProc.  Do not call AVLInsert()
  249.       to insert a node into the tree from inside a walkProc.
  250.       The walkProc function gets called with the AVLTreePtr, a pointer to the data for the
  251.       current node ( which you can change in place as long as you do not affect the order within
  252.       the tree ), the visit stage, the type of the current node ( leaf node, right or left branch,
  253.       or full tree ), the level within the tree ( the root is level 1 ), the balance for the
  254.       current node, and the refCon passed to AVLWalk().  This refCon is different from the one passed
  255.       into AVLInit(); use AVLGetRefCon() to get that refCon if you want it inside a walkProc.
  256.       ( Most walkProcs will not care about the values for node type, level, or balance. )
  257. */
  258. EXTERN_API( OSErr )
  259. AVLWalk                            (AVLTreePtr             tree,
  260.                                  AVLWalkUPP             walkProc,
  261.                                  AVLOrder                 order,
  262.                                  void *                    walkRefCon)                            THREEWORDINLINE(0x303C, 0x0703, 0xAA80);
  263.  
  264. /*    Return  the number of items in the given tree.*/
  265. EXTERN_API( OSErr )
  266. AVLCount                        (AVLTreePtr             tree,
  267.                                  UInt32 *                count)                                THREEWORDINLINE(0x303C, 0x0804, 0xAA80);
  268.  
  269. /*
  270.       Return the one-based index-th item from the tree by putting it's data at dataPtr
  271.       if dataPtr is non-nil, and it's size into *itemSize if itemSize is non-nil.
  272.       If index is out of range, return errItemNotFoundInTree.  ( Internally, this does
  273.       an AVLWalk(), so the tree can not be modified while this call is in progress ).
  274. */
  275. EXTERN_API( OSErr )
  276. AVLGetIndItem                    (AVLTreePtr             tree,
  277.                                  UInt32                 index,
  278.                                  void *                    dataPtr,
  279.                                  UInt32 *                itemSize)                            THREEWORDINLINE(0x303C, 0x0805, 0xAA80);
  280.  
  281. /*
  282.       Insert the given item into the tree.  This will call the tree's sizeItemProc
  283.       to determine how big the item at data is, and then will make a copy of the
  284.       item and insert it into the tree in the appropriate place.  If an item already
  285.       exists in the tree with the same key ( so that the compareItemsUPP returns 0
  286.       when asked to compare this item to an existing one ), then it will return
  287.       errItemNotFoundInTree.
  288. */
  289. EXTERN_API( OSErr )
  290. AVLInsert                        (AVLTreePtr             tree,
  291.                                  const void *            data)                                THREEWORDINLINE(0x303C, 0x0406, 0xAA80);
  292.  
  293. /*
  294.       Remove any item from the tree with the given key.  If dataPtr != nil, then
  295.       copy the item's data to dataPtr before removing it from the tree.  Before
  296.       removing the item, call the tree's disposeItemProc to let it release anything
  297.       used by the data in the tree.  It is not necessary to fill in a complete
  298.       record for key, only that the compareItemsProc return 0 when asked to compare
  299.       the data at key with the node in the tree to be deleted.  If the item cannot
  300.       be found in the tree, this will return errItemNotFoundInTree.
  301. */
  302. EXTERN_API( OSErr )
  303. AVLRemove                        (AVLTreePtr             tree,
  304.                                  const void *            key,
  305.                                  void *                    dataPtr,
  306.                                  UInt32 *                itemSize)                            THREEWORDINLINE(0x303C, 0x0807, 0xAA80);
  307.  
  308. /*
  309.       Find the item in the tree with the given key, and return it's data in
  310.       dataPtr ( if dataPtr != nil ), and it's size in *itemSize ( if itemSize
  311.       != nil ).  It is not necessary to fill in a complete record for key,
  312.       only that the compareItemsProc return 0 when asked to compare the data
  313.       at key with the node in the tree to be deleted.  If the item cannot
  314.       be found in the tree, this will return errItemNotFoundInTree.
  315. */
  316. EXTERN_API( OSErr )
  317. AVLFind                            (AVLTreePtr             tree,
  318.                                  const void *            key,
  319.                                  void *                    dataPtr,
  320.                                  UInt32 *                itemSize)                            THREEWORDINLINE(0x303C, 0x0808, 0xAA80);
  321.  
  322. /*
  323.       Get the refCon for the given tree ( set in AVLInit ) and return it.
  324.       If the given tree is invalid, then return nil.
  325. */
  326. EXTERN_API( OSErr )
  327. AVLGetRefcon                    (AVLTreePtr             tree,
  328.                                  void **                refCon)                                THREEWORDINLINE(0x303C, 0x0409, 0xAA80);
  329.  
  330.  
  331. #if PRAGMA_STRUCT_ALIGN
  332.     #pragma options align=reset
  333. #elif PRAGMA_STRUCT_PACKPUSH
  334.     #pragma pack(pop)
  335. #elif PRAGMA_STRUCT_PACK
  336.     #pragma pack()
  337. #endif
  338.  
  339. #ifdef PRAGMA_IMPORT_OFF
  340. #pragma import off
  341. #elif PRAGMA_IMPORT
  342. #pragma import reset
  343. #endif
  344.  
  345. #ifdef __cplusplus
  346. }
  347. #endif
  348.  
  349. #endif /* __AVLTREE__ */
  350.  
  351.